This is an introductory video to Dynamic Programming.
This track of the course covers the topic "Dynamic Programming".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Dynamic Programming.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This is an introductory video to Dynamic Programming.
This video discusses the memoization implementation of Dynamic Programming- Top-Down Approach.
Codes:
This video talks about tabulation in Dynamic Programming - Bottom-Up Approach
Codes:
This video discusses the Longest Common Subsequence Problem in Dynamic Programming.
Codes:
This is a tabulation solution to the Longest Common Subsequence problem.
Codes:
In this video, we shall discuss a few problems based on the Variation of the Longest Common Subsequence problem.
This video discusses the Coin Change Problem where one needs to count the combinations of the sum.
Codes:
This video discusses the recursive method of solving Edit Distance Problem and various problems involved in the course.
Codes:
This video discusses the Dynamic approach of solving the Edit Distance Problem, in particular, the tabular approach of solving the same.
Codes:
This video introduces us to the Longest Increasing Subsequence problem.
Codes:
This video discusses the Longest Increasing Subsequence Problem involving O(nlogn) time complexity.
Codes:
This video discusses the first variation of Problems based on the Longest Increasing Subsequence concept.
Codes:
This video discusses the second variation of problems based on the Longest Increasing Subsequence Problem.
This video discusses the problem Maximum cut.
Codes:
This video discusses recursive and dynamic programming solutions for the coin change problem.
Codes:
This video discusses the problem of Minimum jumps required to reach end.
Codes:
This video discusses the 0-1 Knapsack problem.
Codes:
Knapsack problem DP approach
Codes:
This video discusses the problem of Optimal Strategy for a game.
Codes:
This video introduces Egg Dropping Puzzle and its recursive solution.
Codes:
This video talks about Dynamic Programming Solution of Egg Dropping Puzzle
Codes:
A recursive structure is discussed, then a dynamic programming solution is discussed, finally relation with Catalan Numbers.
Codes:
Recursive, dynamic programming and space optimized dynamic programming solutions are discussed
Codes:
In this video, a naive recursive solution is discussed. The time complexity of the discussed solution is Theta(2^n)
Codes:
A tabulation based DP solution is discussed which has time complexity O(n * sum)
Codes:
Matrix Chain Multiplication
Codes:
Matrix Chain Multiplication (DP Solution)
Codes:
Palindrome Partitioning
Codes:
We can also see Dynamic Programming as dividing a particular problem into subproblems and then storing the result of these subproblems to calculate the result of the actual problem.
fib(n) = fib(n-1) + fib(n-2), where n >= 2.
and,
fib(0) = 0
fib(1) = 1
1, 1, 2, 3, 5, 8, 13, 21, 34,........
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)

fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Fibonacci number is 102334155
Fibonacci number is 34
That is, say if a problem x is divided into subproblems A and B then the optimal solution of x can be obtained by summing up the optimal solutions to the subproblems A and B.
value[] = {60, 100, 120}
weight[] = {10, 20, 30}
W = 50
Where, value[] is the array containing values of elements,
weight[] is the array containing corresponding weights.
and, W is the weight of Knapsack.
The answer will be 220. We will pick the 2nd and 3rd elements
and add them to the Knapsack for maximum value.
// This function returns the maximum value that canIt should be noted that the above function computes the same subproblems again and again. See the following recursion tree when the above recursive function is evaluated with the sample examples.
// be put in a knapsack of capacity W
int knapSack(int W, int weight[], int value[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;
// If the weight of the nth item is more than Knapsack
// capacity W, then this item cannot be included in
// the optimal solution
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}
In the following recursion tree, K() refers to knapSack(). The two
parameters indicated in the following recursion tree are n and W.
The recursion tree is for following sample inputs.
W = 2, wt[] = {1, 1, 1}, val[] = {10, 20, 30}
K(3, 2) ---------> K(n, W)
/ \
/ \
K(2, 2) K(2, 1)
/ \ / \
/ \ / \
K(1, 2) K(1, 1) K(1, 1) K(1, 0)
/ \ / \ / \
/ \ / \ / \
K(0, 2) K(0, 1) K(0, 1) K(0, 0) K(0, 1) K(0, 0)
Recursion tree for Knapsack capacity 2 units a
nd 3 items of 1 unit weight.
220
Steps to solve a DP 1) Identify if it is a DP problem
2) Decide a state expression with
least parameters
3) Formulate state relationship
4) Do tabulation (or add memoization)
Let's think dynamically about this problem. So, first of all, we decide a state for the given problem. We will take a parameter n to decide state as it can uniquely identify any subproblem. So, our state dp will look like state(n). Here, state(n) means the total number of arrangements to form n by using {1, 3, 5} as elements.
Given 3 numbers {1, 3, 5}, we need to tell
the total number of ways we can form a number 'N'
using the sum of the given three numbers.
(allowing repetitions and different arrangements).
Total number of ways to form 6 is: 8
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
C(5, 2)Since same suproblems are called again, this problem has Overlapping Subproblems property
/ \
C(4, 1) C(4, 2)
/ \ / \
C(3, 0) C(3, 1) C(3, 1) C(3, 2)
/ \ / \ / \
C(2, 0) C(2, 1) C(2, 0) C(2, 1) C(2, 1) C(2, 2)
/ \ / \ / \
C(1, 0) C(1, 1) C(1, 0) C(1, 1) C(1, 0) C(1, 1)
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
int C[n+1][k+1]
// Caculate value of Binomial Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1
// Calculate value using previously stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j]
}
}
return C[n][k]
}
Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 ->9)
First element is 1, so can only go to 3. Second element is 3, so can make at most 3 steps eg to 5 or 8 or 9.// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
// jumps[n-1] will hold the result
int jumps[n]
if (n == 0 || arr[0] == 0)
return INT_MAX;
jumps[0] = 0
// Find the minimum number of jumps to reach arr[i]
// from arr[0], and assign this value to jumps[i]
for (i = 1; i < n; i++)
{
jumps[i] = INT_MAX
for (j = 0; j < i; j++)
{
if (i <= j + arr[j] && jumps[j] != INT_MAX)
{
jumps[i] = min(jumps[i], jumps[j] + 1)
break
}
}
}
return jumps[n-1]
}

Input : arr[] = {3, 10, 2, 1, 20}
Output : Length of LIS = 3
The longest increasing subsequence is 3, 10, 20
Input : arr[] = {3, 2}
Output : Length of LIS = 1
The longest increasing subsequences are {3} and {2}
Input : arr[] = {50, 3, 10, 7, 40, 80}
Output : Length of LIS = 4
The longest increasing subsequence is {3, 7, 40, 80}
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; orTo find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
L(i) = 1, if no such j exists.
lis(4)We can see that there are many subproblems which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.
/ | \
lis(3) lis(2) lis(1)
/ \ /
lis(2) lis(1) lis(1)
/
lis(1)
/* lis() returns the length of the longest increasing
subsequence in arr[ ] of size n */
int lis( int arr[], int n )
{
int lis[n]
lis[0] = 1
/* Compute optimized LIS values in bottom up manner */
for (int i = 1; i < n; i++ )
{
lis[i] = 1;
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1
}
// Return maximum value in lis[]
return *max_element(lis, lis+n)
}

In the following recursion tree, K() refers to knapSack().Since suproblems are evaluated again, this problem has Overlapping Subprolems property. So the 0-1 Knapsack problem has both properties -
The two parameters indicated in the following recursion tree are n and W.
The recursion tree is for following sample inputs.
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}
K(3, 2) ---------> K(n, W)
/ \
/ \
K(2,2) K(2,1)
/ \ / \
/ \ / \
K(1,2) K(1,1) K(1,1) K(1,0)
/ \ / \ / \
/ \ / \ / \
K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0)
Recursion tree for Knapsack capacity 2 units and 3 items of 1 unit weight.
// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int K[n+1][W+1]
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else
K[i][w] = K[i-1][w]
}
}
return K[n][W]
}
Asked In: Amazon
Asked In: Amazon
Asked In: Amazon
Asked In: Amazon
A | Bellman–Ford Algorithm for single source shortest path |
B | Floyd Warshall Algorithm for all pairs shortest paths |
C | 0-1 Knapsack problem |
D | Prim's Minimum Spanning Tree |